package william.recursive;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhangShenao
 * @date 2024/3/29
 * @description <a href="https://leetcode.cn/problems/integer-break/description/">...</a>
 */
public class Leetcode343_整数拆分 {
    /**
     * 使用Map保存中间结果,减少重复计算
     */
    private Map<Integer, Integer> cache = new HashMap<>();

    /**
     * 采用递归算法实现：记忆化搜索
     * 递推公式: n拆分后乘积的最大值 = 1*(n-1)拆分的最大值, 2*(n-2)拆分的最大值, .... ,(n-1)*1拆分的最大值
     * 使用Map保存中间结果,减少重复计算
     * <p>
     * 时间复杂度O(N^N)
     * 空间复杂度
     */
    public int integerBreak(int n) {
        //递归终止条件
        if (n <= 1) {
            return 1;
        }

        //首先尝试从缓存中查找
        if (cache.containsKey(n)) {
            return cache.get(n);
        }

        //递推公式: n拆分后乘积的最大值 = 1*(n-1)拆分的最大值, 2*(n-2)拆分的最大值, .... ,(n-1)*1拆分的最大值
        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= n - 1; i++) {
            max = Math.max(Math.max(max, i * (n - i)), i * integerBreak(n - i));
        }

        //将结果保存至缓存
        cache.put(n, max);

        //返回最大值
        return max;
    }

}
